High Efficiency Video Coding (HEVC) is the latest international video coding standard developed by the Joint Collaborative Team on Video Coding (JCT-VC) group of video coding experts from ITU-T Study Group. The HEVC standard relies on a block-based coding structure which divides a picture into multiple non-overlapped square Coding Tree Units (CTUs). Each CTU consists of multiple Coding Tree Blocks (CTBs) and each CTB is for one color component. The CTUs in a slice are processed according to a raster scan order; and each CTU is further recursively divided into Coding Units (CUs) according to a quadtree partitioning method to adapt to various local characteristics. FIG. 1 illustrates an exemplary system block diagram of a Video Encoder 100 based on the HEVC standard. Intra Prediction 110 provides intra predictors based on reconstructed blocks of a current picture, and Inter Prediction 112 performs motion estimation (ME) and motion compensation (MC) to provide inter predictors based on video data from other picture or pictures. Switch 114 selects an intra predictor from Intra Prediction 110 or an inter predictor from Inter Prediction 112 for each block in the current picture. The selected predictor is supplied to Adder 116 to be subtracted from the input video data in order to form prediction errors, also called residues. The prediction errors are then processed by Transformation (T) 118 followed by Quantization (Q) 120. The transformed and quantized residues are then coded by Entropy Encoder 134 to form a video bitstream corresponding to the compressed video data. The video bitstream associated with the transform coefficients is then packed with side information. The side information may also be subject to entropy coding to reduce required bandwidth, and the data associated with the side information are provided to Entropy Encoder 134 as shown in FIG. 1. When an inter prediction mode is selected, a reference picture or pictures have to be reconstructed at the encoder end as well. Consequently, the transformed and quantized residues are processed by Inverse Quantization (IQ) 122 and Inverse Transformation (IT) 124 to recover the residues. The residues are then added back to the selected predictors at Reconstruction (REC) 126 to produce reconstructed blocks. The reconstructed blocks may be stored in Reference Picture Buffer 132 and used for prediction of other pictures.
As shown in FIG. 1, incoming video data undergoes a series of video processing in the video encoding system. The reconstructed blocks generated from REC 126 may be subject to various impairments due to a series of encoding processing. Accordingly, various in-loop processing is applied to the reconstructed blocks before the reconstructed blocks are stored in the Reference Picture Buffer 132 in order to improve video quality. In the HEVC standard, Deblocking Filter (DF) 128 and Sample Adaptive Offset (SAO) 130 are applied to the reconstructed blocks before storing in the Reference Picture Buffer 132 to enhance picture quality. The in-loop filter information may have to be incorporated in the video bitstream so that a decoder can properly recover the required information.
FIG. 2 illustrates a system block diagram of an exemplary HEVC-based Video Decoder 200. Entropy Decoder 210 is used to parse and recover the coded syntax elements related to residues, motion information and other control data. Switch 216 selects Intra Prediction 212 or Inter Prediction 214 according to decoded mode information, and the selected predictors are supplied to reconstruction (REC) 218 to be combined with the recovered residues. Besides performing entropy decoding on compressed video data, Entropy Decoder 210 is also responsible for entropy decoding of side information and provides the side information to respective blocks. For example, intra mode information is provided to Intra Prediction 212, inter mode information is provided to Inter Prediction 214, sample adaptive offset information is provided to SAO 226 and residues are provided to Inverse Quantization (IQ) 220. The residues are processed by IQ 220, Inverse Transformation (IT) 222 and subsequent reconstruction process to produce reconstructed blocks. The reconstructed blocks are further processed by DF 224 and SAO 226 to generate final decoded video. If the currently decoded picture is a reference picture, the final decoded video of the currently decoded picture is also stored in Ref. Pict. Buffer 228 for later pictures in decoding order.
FIG. 3A illustrates an example of the quadree (QT) partitioning method applied in the HEVC standard to split a block into four smaller sub-blocks. Alternative partitioning methods called binary tree (BT) block partitioning and triple tree (TT) block partitioning split a block into two smaller sub-blocks and three smaller sub-blocks respectively. FIGS. 3B and 3C illustrate symmetrical vertical splitting and symmetrical horizontal splitting according to binary tree block partitioning. For a given block of size M×N, the size of the two smaller sub-blocks is M/2×N if symmetrical vertical splitting is used; otherwise the size is M×N/2 if symmetrical horizontal splitting is used. Triple tree partitioning method is designed to capture objects which locate in the block center while quadtree and binary tree partitioning methods always split along the block center. FIG. 3D illustrates vertical center-side triple tree partitioning, and FIG. 3E illustrates horizontal center-side triple tree partitioning. The triple tree partitioning method may provide capability to faster localize small object along block boundaries, by allowing one-quarter partitioning vertically or horizontally.
Although the binary tree and triple tree partitioning methods supports more partition shapes and thus is more flexible than the quadtree partitioning method, the coding complexity and signaling overhead increase for selecting the best partition shape among all possible partition shapes. A combined partitioning method called Quad-Tree-Binary-Tree (QTBT) structure combines a quadtree partitioning method with a binary tree partitioning method, which balances the coding efficiency and the coding complexity of the two partitioning methods. An exemplary QTBT structure is shown in FIG. 4A, where a given block such as a CTU is first partitioned by a quadtree partitioning method then a binary tree partitioning method. FIG. 4A illustrates an example of block partitioning structure according to the QTBT partitioning method and FIG. 4B illustrates a coding tree diagram for the QTBT block partitioning structure shown in FIG. 4A. The solid lines in FIGS. 4A and 4B indicate quadtree partitioning while the dotted lines indicate binary tree partitioning. In each non-leaf splitting node of the binary tree structure, one flag indicates which splitting type is used, 0 indicate symmetrical horizontal splitting and 1 indicates symmetrical vertical splitting. The QTBT partitioning method may be used to split a CTU into CUs, where the CUs are called binary tree leaf nodes and are used for prediction and transform without any further partitioning.
Multi-Type-Tree (MTT) block partitioning extends the concept of the two-level tree structure in QTBT by allowing both the binary tree and triple tree partitioning methods in the second level of MTT. The two levels of trees in MTT are called region tree (RT) and prediction tree (PT) respectively. The first level RT is always quadtree (QT) partitioning, and the second level PT may be either binary tree (BT) partitioning or triple tree (TT) partitioning. For example, a CTU is firstly partitioned by RT, which is QT partitioning, and each RT leaf node may be further split by PT, which is either BT or TT partitioning. A block partitioned by PT may be further split with PT until a maximum PT depth is reached, for example, a block may be first partitioned by vertical BT partitioning to generate a left sub-block and a right sub-block, and the left sub-block is further split by horizontal TT partitioning while the right sub-block is further split by horizontal BT partitioning. A PT leaf node is the basic Coding Unit (CU) for prediction and transform and will not be further split.
FIG. 5 illustrates an example of tree-type signaling for block partitioning according to MTT block partitioning. RT signaling may be similar to the quadtree signaling in QTBT block partitioning. For signaling a PT node, one additional bin is signaled to indicate whether it is a binary tree partitioning or triple tree partitioning. For a block split by RT, a first bin is signaled to indicate whether there is another RT split, if the block is not further split by RT (i.e. the first bin is 0), a second bin is signaled to indicate whether there is a PT split. If the block is also not further split by PT (i.e. the second bin is 0), then this block is a leaf node. If the block is then split by PT (i.e. the second bin is 1), a third bin is sent to indicate horizontal or vertical partitioning followed by a fourth bin for distinguishing binary tree (BT) or triple tree (TT) partitioning.
While the proposed MTT is able to improve performance by adaptively partitioning blocks for prediction and transform, it is desirable to further improve the performance whenever possible in order to achieve an overall efficiency target.